package com.leetcode.algorithm.y22.m08.w3;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 187. 重复的DNA序列
 * 
 * https://leetcode.cn/problems/repeated-dna-sequences/
 * 
 * @author jie.deng
 *
 */
class Question0187Solution01 {
	
	public List<String> findRepeatedDnaSequences(String s) {
		List<String> result = new ArrayList<>();
		int len = s.length();
		if (len <= 10) {
			return result;
		}
		Set<Integer> numSet = new HashSet<>();
		Set<Integer> resultSet = new HashSet<>();
		int idx = 0;
		int num = 0;
		while (idx < 10) {
			num <<= 2;
			char ch = s.charAt(idx);
			if (ch == 'A') {
				num |= 0;
			} else if (ch == 'C') {
				num |= 1;
			} else if (ch == 'G') {
				num |= 2;
			} else if (ch == 'T') {
				num |= 3;
			}
			idx++;
		}
		numSet.add(num);

		while (idx < len) {
			num &= 0x3ffff;
			num <<= 2;
			char ch = s.charAt(idx);
			if (ch == 'A') {
				num |= 0;
			} else if (ch == 'C') {
				num |= 1;
			} else if (ch == 'G') {
				num |= 2;
			} else if (ch == 'T') {
				num |= 3;
			}
			if (!resultSet.contains(num)) {
				if (!numSet.add(num)) {
					resultSet.add(num);
					result.add(s.substring(idx - 9, idx + 1));
				}
			}
			idx++;
		}

		return result;
	}
    
}